#include<bits/stdc++.h>
using namespace std;

// 定义最大城市数量和状态数量，以及无穷大的值
const int Maxn = 25, MaxN = 5e5 + 5;
const int Inf = 1e8 + 9;
int n, N;

// 存储城市间网络通路的成本
int Link[Maxn][Maxn];
// f数组存储状态u时，包含点x的最小成本
int f[MaxN][Maxn], num[MaxN];
// g数组存储状态u时，不包含点x的最小成本
int g[MaxN][Maxn];

/**
 * 计算状态u中包含点x的最小成本
 * @param u 状态表示
 * @param x 当前考虑的点
 */
void getf(int u, int x)
{
    // 如果状态u中不包含点x，直接返回
    if((u & (1 << x)) == 0) return;
    
    // 如果状态u中只包含一个点，直接将f[u][x]置为0
    if(num[u] == 1)
    {
        f[u][x] = 0;
    }
    else
    {
        // 初始化一个很大的数，表示无穷大
        int res = Inf;
        // 遍历状态u的所有子集
        for(int i = (u - 1) & u; i; i = (i - 1) & u)
        {
            // 如果子集中不包含点x，跳过
            if((i & (1 << x)) == 0) continue;
            
            // 将状态u分为两部分：子集i和u^i
            int s = i, t = u ^ s;
            
            // 如果子集s中只有点x，直接跳出循环
            if(f[s][x] == Inf)
            {
                if(s == (1 << x)) break;
                continue;
            }
            
            // 更新最小值
            res = min(res, f[s][x] + g[t][x]);
            
            // 如果子集s中只有点x，直接跳出循环
            if(s == (1 << x)) break;
        }
        
        // 更新f[u][x]的值
        f[u][x] = min(f[u][x], res);
    }
    
    // 更新g[u][i]的值
    for(int i = 0; i < n; i++)
    {
        if(Link[x][i] == Inf) continue;
        g[u][i] = min(g[u][i], f[u][x] + Link[x][i] * num[u] * (n - num[u]));
    }
}

/**
 * 主处理函数
 * 解决问题：计算所有城市间传输时间的和的最小值
 */
void solve()
{
    int m;
    cin >> n >> m;
    
    // 初始化Link数组为无穷大
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            Link[i][j] = Inf;
        }
    }
    
    // 输入网络通路及其成本
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        Link[x][y] = Link[y][x] = min(Link[x][y], z);
    }
    
    // 初始化状态数组
    N = (1 << n);
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < n; j++)
        {
            f[i][j] = g[i][j] = Inf;
            if(i & (1 << j))
            {
                num[i]++;
            }
        }
    }
    
    // 动态规划计算所有状态下的最小成本
    for(int i = 1; i < N; i++)
    {
        for(int j = 0; j < n; j++)
        {
            getf(i, j);
        }
    }
    
    // 寻找最终答案
    int ans = Inf;
    for(int i = 0; i < n; i++)
    {
        ans = min(ans, f[N - 1][i]);
    }
    
    // 如果没有找到有效解，设置为-1
    if(ans == Inf) ans = -1;
    
    // 输出结果
    cout << ans << "\n";
}

// 主函数入口
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    solve();
    return 0;
}
